# Dynamic Programming
#
# Rod cutting code for Python
#
# simonwoo2000@gmail.com
#
# bottom-up method

import math

prices = {
          1:1,
          2:5,
          3:8,
          4:9,
          5:10,
          6:17,
          7:17,
          8:20,
          9:24,
          10:30
          }

optsize2r = {0:0}

def maxr(n):
    for i in range(1,n+1):
        r=0
        if i==4:
            pass
        for j in range(1,i+1):
            r=max(prices[j]+optsize2r[i-j],r)
        optsize2r[i] = r
    
    print(optsize2r[n])


if __name__=='__main__':
    maxr(10)
    pass
